<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>双向链表</title>
</head>
<body>
<script>
  function DoublyLinkedList() {

    function Node(data) {
      this.data = data;
      this.prev = null;
      this.next = null;
    }

    this.head = null;
    this.tail = null;
    this.length = 0;

    // 1. 向链表中追加元素
    DoublyLinkedList.prototype.append = function (data) {
      let newNode = new Node(data)

      if (this.length === 0) {
        this.head = newNode
        this.tail = newNode
      } else {
        this.tail.next = newNode
        newNode.prev = this.tail
        this.tail = newNode
      }
      this.length++
    }
    // 2. 在指定位置插入元素
    DoublyLinkedList.prototype.insert = function (position, data) {
      if (position < 0 || position > this.length) {
        return false
      }
      let newNode = new Node(data);

      if (this.length === 0) {
        this.head = newNode
        this.tail = newNode
      } else {
        if (position === 0) {
          this.head.prev = newNode
          newNode.next = this.head
          this.head = newNode
        } else if (position === this.length) {
          this.tail.next = newNode
          newNode.prev = this.tail
          this.tail = newNode
        } else {
          let current = this.head
          let index = 0
          while (index++ < position) {
            current = current.next
          }
          newNode.next = current
          newNode.prev = current.prev
          current.prev.next = newNode
          current.prev = newNode
        }
      }
      this.length++
      return true
    }

    DoublyLinkedList.prototype.get = function (position) {
      if (position < 0 || position >= this.length) {
        return null
      }
      let current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
      return current.data
    }

    DoublyLinkedList.prototype.indexOf = function (data) {
      let current = this.head
      let index = 0
      while (current) {
        if (current.data === data) {
          return index
        }
        current = current.next
        index++
      }
      return -1
    }

    DoublyLinkedList.prototype.update = function (position, data) {
      if (position < 0 || position >= this.length) {
        return false
      }
      let current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
      current.data = data
      return true
    }

    DoublyLinkedList.prototype.removeAt = function (position) {
      if (position < 0 || position >= this.length) {
        return null
      }
      let current = this.head
      if (this.length === 1) {
        this.head = null
        this.tail = null
      } else {
        if (position === 0) {
          this.head.next.prev = null
          this.head = this.head.next
        } else if (position === this.length - 1) {
          current = this.tail
          this.tail.prev.next = null
          this.tail = this.tail.prev
        } else {
          let index = 0
          while (index++ < position) {
            current = current.next
          }
          current.prev.next = current.next
          current.next.prev = current.prev
        }
      }
      this.length--
      return current.data
    }

    DoublyLinkedList.prototype.isEmpty = function() {
      return this.length === 0
    }

    DoublyLinkedList.prototype.size = function() {
      return this.length
    }

    DoublyLinkedList.prototype.remove = function(data) {
      let position = this.indexOf(data);
      return this.removeAt(position)
    }

    DoublyLinkedList.prototype.toString = function () {
      return this.backwardString();
    }

    DoublyLinkedList.prototype.forwardString = function () {
      let current = this.tail
      let result = '';
      while (current) {
        result += current.data + " "
        current = current.prev
      }
      return result;
    }

    DoublyLinkedList.prototype.backwardString = function () {
      let current = this.head
      let result = '';
      while (current) {
        result += current.data + " "
        current = current.next
      }
      return result;
    }
  }

  let list = new DoublyLinkedList();
  list.append("aaa");
  list.append("bbb");
  list.append("ccc");
  list.append("ddd");

  alert(list.removeAt(2))


</script>
</body>
</html>